#include <iostream>
#include <vector>
#include <map>

using std::cout;
using std::endl;
using std::vector;
using std::map;

class Solution {
public:
    /*      1, 3, 5, 4, 7
        状态转移方程：
            dp[0] = 1
            dp[1] = max{1, if dp[1] > dp[0] -> 1 + dp[0]} = 2
            
            dp[i] = max{1, 
                for(int j{i - 1}; j >= 0; j++){
                    if(dp[i] > dp[j])
                }
            }
    */
    int findNumberOfLIS(const vector<int>& nums) {
        vector<int> dp;
        dp.resize(nums.size());
        dp[0] = 1;
        int globalMax = 1, total = 0;
        map<int, int> mp;
        for(int i{1}; i < nums.size(); i++){
            int tmpMax = 1;
            for(int j{i - 1}; j >= 0; j--){
                if(nums[i] > nums[j] && dp[j] + 1 >= tmpMax){
                    tmpMax = dp[j] + 1;
                    mp[tmpMax]++;
                }
            }
            dp[i] = tmpMax;
            if(globalMax < tmpMax){
                globalMax = tmpMax;
            }
        }

        for(auto [k, v]: mp){
            cout << k << ": " << v << endl;
        }

        return mp.size() > 0 ? mp[globalMax] : nums.size();
    }
};

int main(int argc, char const *argv[])
{
    /* code */
    Solution sol;
    cout << sol.findNumberOfLIS({1,2,4,3,5,4,7,2}) << endl;
    return 0;
}
